1. Field of the Invention
The present invention relates to a parallel allocation optimization device, a parallel allocation optimization method and a computer-readable recording medium which optimize data allocated in each parallel processing.
2. Description of Related Art
In recent years, a technique is becoming important which analyzes “sparse” data which is large and in which most elements in data are zero elements such as text word vector data, a disease log (a logical value vector as to whether or not disease is developing) or a purchase history (a logical value vector as to whether or not a product is bought).
An efficient data structure utilizing for sparse data the fact that elements of data are 0 and a calculating technique are studied and developed. Such a data structure is, for example, a sparse data structure which stores positions and values of nonzero elements. Further, this calculating technique is, for example, a sparse matrix operation of only multiplying nonzero elements using the property that 0 is 0 no matter what 0 is multiplied with any number.
Furthermore, in recent years, “lazy update” using sparsity of data in a machine learning field is proposed. This is a technique of increasing a learning processing speed by “delaying” an update of zero elements of data in a learning machine adopting a special parameter optimization rule.
Non Patent Literature (NPTL) 1 describes a method of optimizing a learning machine. Hereinafter, a case will be described as an example where a lazy update rule is applied to a linear discriminant/regression model described in NPTL1. An update rule described in NPTL1 is an update rule without delay. More specifically, the update rule described in NPTL1 optimizes the learning machine by repeating a first updating step of a gradient direction of a loss function and a second updating step of a model regularization function.
According to the update rule described in NPTL1, when data elements are zero, the gradient of the loss function is zero. Hence, when items of data having values of zero are successive, only the second updating step is repeated. In this case, calculation of the second updating step can be essentially executed collectively a plurality of times. Hence, when a lazy update is applied to this processing, an update is not performed while data having zero elements are successive and an update is delayed when data having a nonzero element appears, so that it is possible to collectively perform the second updating step. Consequently, it is possible to substantially reduce the calculation amount.